void print(int line, int *line1, int *line2, int n)
{
  int i = 0;
  int linex = 0;
  
  linex = line;
  
  for(i=n-1; i>=0; i--)
  {
    printf("line:%d, station:%d:\n", linex, i+1);
    if(1 == linex)
    {
      linex = line1[i];
    }
    else
    {
      linex = line2[i];
    }
  }
}

void printx(int line, int *line1, int *line2, int n)
{
  if (0 == n)
  {
    //printf("line:%d, station:%d\n", line, n+1);
    return;
  }
  else
  {
    if(1 == line)
    {
      printx(line1[n-1], line1, line2, n-1);
    }
    else
    {
      printx(line2[n-1], line1, line2, n-1);
    }
  }

  printf("line:%d:, station:%d\n", line , n);
}

void FastestWay(int *e, int *x, int *S1, int *S2, int*T1, int *T2, int n)
{
  int f1 = e[0]+S1[0];
  int f2 = e[1]+S2[0];

  int i = 0;
  int total;
  int oldf1 = 0;
  int oldf2 = 0;
  int line1[10] = {0};
  int line2[10] = {0};
  line1[0] = 1;
  line2[0] = 2;
  for(i=1; i<n; i++)
  {
	oldf1 = f1;
	oldf2 = f2;
    if(oldf1+S1[i] < oldf2+T2[i-1]+S1[i])
	{
	  line1[i] = 1;
	  f1 = oldf1+S1[i];
	}
    else
	{
          line1[i] = 2;
	  f1 = oldf2+T2[i-1]+S1[i];
	}
    if(oldf2+S2[i] < oldf1+T1[i-1]+S2[i])
	{
          line2[i] = 2;
	  f2 = oldf2+S2[i];
	}
    else
	{
	  line2[i] = 1;
          f2 = oldf1+T1[i-1]+S2[i];
	}
  }

  if(f1+x[0] < f2+x[1])
  {
    total = f1+x[0];
  }
  else
  {
    total = f2+x[1];
  }
    printx(1,line1, line2, 6);
}

void PrintChain(int m[][10], int i, int j)
{
  if(i == j)
  {
    printf(" A%d ", i);
  }
  else
  {
    printf(" ( ");
    PrintChain(m, i, m[i][j]);
    PrintChain(m, m[i][j]+1, j);
    printf(" ) ");
  }

}

void Matrix_Chain_Order(int *p, int length)
{
  int n = length - 1;
  int m[10][10] = {0};
  int s[10][10] = {0};
  
  int i = 0;
  int j = 0;
  int k = 0;
  int l = 0;
  int q = 0;
  for(int i=1; i<=n; i++)
  {
    m[i][i] = 0;
  }
  for(l=2; l<=n; l++)
  {
    for(i=1; i<=n-l+1; i++)
    {
      j = i+l-1;
      m[i][j] = 100000;

      for(k=i; k<=j-1; k++)
      {
        q = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
        if(q<m[i][j])
        {
          m[i][j] = q;
          s[i][j] = k;
        }
      }
    }
  }

  PrintChain(s, 1, 6);
}


int LCS(char *S1, int n1, char *S2, int n2)
{
  int c[10][10] = {0};
  int i = 0;
  int j = 0;
  for(i=1; i<=n1; i++)
  {
    for(j=1; j<=n2; j++)
    {
      if(S1[i-1] == S2[j-1])
      {
        c[i][j] = c[i-1][j-1] +1;
      }
      else
      {
        if(c[i-1][j] >= c[i][j-1])
	{
	  c[i][j] = c[i-1][j];
	}
	else
	{
	  c[i][j] = c[i][j-1];
	}
      }
    }
  }
  for(i=0; i<=n1; i++)
  {
    for(j=0; j<=n2; j++)
      printf("%d  ", c[i][j]);
    printf("\n");
  }

  i=n1;
  j=n2;
  while(i>0 && j>0)
  {
	/*
    if((0==i || 0==j) && c[i][j] != 0)
    {
      printf("%c  ", S2[j-1]);
    }*/
    if(c[i][j] == c[i-1][j-1]+1)
    {
      printf("%c  ", S2[j-1]);
      i--;
      j--;
    }
    else
    {
      j--; 
    }
  }
  return 0;
}

